// https://leetcode.cn/problems/copy-list-with-random-pointer/
// Created by ade on 2022/7/27.
//
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Node {
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
public:
    unordered_map<Node *, Node *> myMap;

    Node *copyRandomList(Node *head) {
        return dfs(head);
    }

    Node *dfs(Node *old) {
        if (!old) return nullptr;
        if (myMap.find(old) != myMap.end()) {
            return myMap[old];
        }
        Node *newNode = new Node(old->val);
        myMap[old] = newNode;
        newNode->next = dfs(old->next);
        newNode->random = dfs(old->random);
        return newNode;
    }
};

int main() {

}